The efficiency of a nucleic acid modifying enzyme, i.e., the amount of modified product generated by the enzyme per binding event, can be enhanced by increasing the stability of the modifying enzyme/nucleic acid complex. The prior art has suggested that attachment of a high probability binding site, e.g., a positively charged binding tail, to a nucleic acid modifying enzyme can increase the frequency with which the modifying enzyme interacts with the nucleic acid (see, e.g. U.S. Pat. No. 5,474,911). The present invention now provides novel modifying enzymes in which the double-stranded conformation of the nucleic acid is stabilized and the efficiency of the enzyme increased by joining a sequence-non-specific double-stranded nucleic acid binding domain to the enzyme, or its catalytic domain. The modifying proteins that are processive in nature exhibit increased processivity when joined to a binding domain compared to the enzyme alone. Moreover, both processive and non-processive modifying enzymes exhibit increased efficiency at higher temperatures when joined to a typical binding domain described herein.